In the field of computer systems, cache memories and their use are well known. However, a brief discussion follows in so far as is necessary to fully understand this invention.
Caches are high-cost, high-speed memories that provide an important performance optimisation in processors. This is done by keeping copies of the contents of most commonly used locations of main memory near to the processor, namely in cache locations. As a result, accesses to the contents of these memory locations are much quicker.
The instruction cache is responsible for optimising accesses to the program being executed. The cache will usually be smaller than the size of the program, meaning that the contents of the cache will need to change to ensure that the parts of the program currently being executed are in the cache.
In designing the instruction cache a trade-off between cost and performance has to be made. Two of the key parameters that can be changed are the cache's size and associativity. These both influence the resulting silicon area and maximum clock frequency of the cache.
The size of a cache is determined by a number of factors, but will depend primarily on area limitations and target applications of the design.
Determining the appropriate level of associativity of the cache can be harder.
For a direct-mapped cache, each block in main memory maps to a unique location (line) in the cache, That is a “block” in memory is a chunk of data corresponding in size to a cache location. If two blocks map to the same line then they cannot be in the cache at the same time and will continually replace each other. This case is referred to as a conflict.
For a set-associative cache, each block maps to a set of lines. The block can be stored in any of the lines in the set. Note that because the number of lines in the cache is constant, dividing the cache into sets means that more blocks map to each set. In general, the cache will be more effective with a reasonable level of associativity because it can decide which lines it will replace and which lines will be kept.
However, there are at least two reasons why a direct-mapped cache may be chosen, namely higher potential clock frequency and smaller area than a set-associative cache of the same size.
One of the disadvantages of a direct-mapped instruction cache manifests itself in relation to functions which desirably should be locked into a cache. There are a number of cases where it is desirable to lock a function into the cache. For example, an interrupt handler routine may have to guarantee a maximum latency for treating the interrupt. This may only be possible if the code is locked into the cache. However, in a direct-mapped cache, each memory block maps to a single entry in the cache, For this reason it is not common to provide cache locking with a direct-mapped cache. That is, if an area of memory were locked into the cache, then any other code that maps to the same position would have to be executed uncached. In some cases, executing code uncached may not be supported, and therefore locking a part of the cache would prevent normal programs from being executed.
Thus, in general, cache locking is provided only with set associative caches which do not have the same limitation on mapping of code into the cache.
It is an aim of the present invention to allow cache locking to be implemented with a direct-mapped cache without need for additional hardware.
According to one aspect of the invention there is provided a method of linking a plurality of object files to generate an executable program, the method comprising: identifying in the object files at least one routine to be locked into a cache when the program is executed; locating said routine at a set of memory addresses which map onto a set of cache locations; introducing into the executable program gaps at other sets of memory addresses which map onto the same set of cache locations.
Another aspect of the invention provides a linker for linking a plurality of object files to generate an executable program, the linker comprising: means for identifying in the object files at least one routine to be locked into a cache when the program is executed; means for locating said routine at a set of memory addresses which map onto a set of cache locations: and means for introducing into the executable program gaps at other sets of memory addresses which map onto the same set of cache locations.
A further aspect of the invention provides a computer program product comprising program code means in the form of an executable program containing a plurality of routines, wherein at least one of said routines is located at a set of memory addresses which map onto a set of cache locations and wherein at other sets of memory addresses which map onto the same set of cache locations the executable program contains gaps, whereby when the computer program product is loaded into a computer and executed, said at least one routine is locked into the cache.
For a better understanding of the present invention and to show how the same may be carried into effect, reference will now be made by way of example to the accompanying drawings.